package org.hot100.h033;

/**
 * @Author: wjy
 * @Date: 2021/12/10 17:39
 */
public class Solution {

    public static void main(String[] args) {

        int[] ints = {4, 5, 6, 7, 8, 9, 0, 1, 2};
        //int[] ints = {3, 1};
        Solution solution = new Solution();
        System.out.println(solution.search4(ints, 7));

    }

/*    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }*/

    /**
     * 二分查找
     *
     * @param nums
     * @param target
     * @return int
     */
    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1, mid = 0;

        while (true) {

            mid = (left + right) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // 当left == right时返回-1
            if (left == right) {
                return -1;
            }

            // 判断左侧是否为有序字段
            if (nums[left] <= nums[mid]) {

                // 当左侧为有序时，判断target是否在左侧范围内
                if (target < nums[mid] && target >= nums[left]) { // 此处注意⚠️ target >= nums[left] 考虑等于问题
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }

            } else {

                // 当左侧树无序时，判断target是否在右侧范围内
                if (target > nums[mid] && target <= nums[right]) { // 此处注意⚠️ target <= nums[right] 考虑等于问题
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }

            }

        }
    }

    // 4, 5, 6, 7, 8, 9, 0, 1, 2
    public int search2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] <= nums[mid]) {
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public int search3(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {

            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] < nums[mid]) {
                if (nums[left] <= target && nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && nums[right] >= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

        }
        return -1;
    }

    public int search4(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] < nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[right] >= target && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

}
